package pers.tz.题目.leetcode.树;

import pers.tz.common.TreeNode;

/**
 * @author irony
 * @date 2024-03-13
 */
public class leetcode_0098_验证二叉搜索树 {
//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//
// 有效 二叉搜索树定义如下：
// 节点的左子树只包含 小于 当前节点的数。
// 节点的右子树只包含 大于 当前节点的数。
// 所有左子树和右子树自身必须也是二叉搜索树。
//
// 示例 1：
//输入：root = [2,1,3]
//输出：true
//
// 示例 2：
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
//
// 提示：
// 树中节点数目范围在[1, 10⁴] 内
// -2³¹ <= Node.val <= 2³¹ - 1
    public static void main(String[] args) {

    }

    public static boolean isValidBST(TreeNode root) {
        return process(root).bst;
    }

    public static Info process(TreeNode root) {
        if (root == null) {
            // 上游处理
            return null;
        }

        Info left = process(root.left);
        Info right = process(root.right);

        boolean bst = true;
        if (left != null && !left.bst) {
            bst = false;
        }
        if (right != null && !right.bst) {
            bst = false;
        }
        if (left != null && left.max >= root.val) {
            bst = false;
        }
        if (right != null && right.min <= root.val) {
            bst = false;
        }

        int max = root.val;
        if (left != null) {
            max = Math.max(left.max, max);
        }
        if (right != null) {
            max = Math.max(right.max, max);
        }

        int min = root.val;
        if (left != null) {
            min = Math.min(left.min, min);
        }
        if (right != null) {
            min = Math.min(right.min, min);
        }

        return new Info(bst, max, min);
    }

    // 1. 左树是搜索二叉树
    // 2. 右树是搜索二叉树
    // 3. 左树的最大值比root.val小
    // 4. 右树的最小值比root.val大

    // 左树和右树提的要求不一样，求全集
    // 递归 一视同仁的递归
    public static class Info {
        public boolean bst;
        public int max;
        public int min;

        public Info() {
        }

        public Info(boolean bst, int max, int min) {
            this.bst = bst;
            this.max = max;
            this.min = min;
        }
    }
}
